home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-04 / bipl.zip / PROGS.ZIP / PARGEN.ICN < prev    next >
Text File  |  1992-11-26  |  6KB  |  201 lines
  1. ############################################################################
  2. #
  3. #    File:     pargen.icn
  4. #
  5. #    Subject:  Program to generate context-free parser
  6. #
  7. #    Author:   Ralph E. Griswold
  8. #
  9. #    Date:     March 31, 1992
  10. #
  11. ###########################################################################
  12. #
  13. #     This program reads a context-free BNF grammar and produces an Icon
  14. #  program that is a parser for the corresponding language.
  15. #
  16. #     Nonterminal symbols are are enclosed in angular brackets. Vertical
  17. #  bars separate alternatives.  All other characters are considered to
  18. #  be terminal symbols.  The nonterminal symbol on the first line is
  19. #  taken to be the goal.
  20. #
  21. #     An example is:
  22. #
  23. #    <expression>::=<term>|<term>+<expression>
  24. #    <term>::=<element>|<element>*<term>
  25. #    <element>::=x|y|z|{<expression>}
  26. #
  27. #     Parentheses can be used for grouping symbols, as in
  28. #
  29. #    <term>::=<element>(|*<term>)
  30. #
  31. #     Note that an empty alternative is allowable.
  32. #
  33. #     The right-hand side metacharacters <, >, (, ), and | are accessible
  34. #  through the built-in symbols <lb>, <rb>, <lp>, <rp>, and <vb>,
  35. #  respectively. There are two other build-in symbols, <empty> and <nl>
  36. #  that match the empty string and a newline, respectively.
  37. #
  38. #     Characters in nonterminal names are limited to letters, digits, and
  39. #  underscores.
  40. #
  41. #     An underscore is appended to the parsing procedure name to avoid
  42. #  possible collisions with Icon function names.
  43. #
  44. #     Lines beginning with an = are passed through unchanged. This allows
  45. #  Icon declarations to be placed in the parser.  Lines beginning with
  46. #  a # are considered to be comments and are ignored.
  47. #
  48. #     If the name of a ucode file is given on the command line, a link
  49. #  declaration for it is provided in the output. Otherwise the main
  50. #  procedure in recog is used.
  51. #
  52. ############################################################################
  53. #
  54. #  Limitations:
  55. #
  56. #     Left recursion in the grammar may cause the parser to loop.
  57. #  There is no check that all nonterminal symbols that are referenced
  58. #  are defined or that there may be duplicate definitions.
  59. #
  60. ############################################################################
  61. #
  62. #  Reference:
  63. #
  64. #     The Icon Programming Language, Second Edition, Ralph E. and Madge T.
  65. #     Griswold, Prentice-Hall, 1990, pp. 180-187.
  66. #
  67. ############################################################################
  68. #
  69. #  Output links recog, matchlib
  70. #
  71. #  See also: recog.icn, matchlib.icn, and parscond.icn
  72. #
  73. ############################################################################
  74.  
  75. global declend            # name suffix and record body
  76. global goal            # nonterminal goal name
  77. global nchars            # characters allowed in a nonterminal name
  78. global procend            # name suffix and parens
  79. global sym            # current nonterminal symbol
  80.  
  81. procedure main(args)
  82.    local line            # a line of input
  83.  
  84.    declend := "__"
  85.    procend := "_()"
  86.    nchars := &letters ++ &digits ++ '_'
  87.  
  88.    while line := read() do {        # process lines of input
  89.       line ? {
  90.          case move(1) of {        # action depends on first character
  91.             "<":  tab(0) ? transprod()    # transform the production
  92.             "=":  write(tab(0))        # pass through
  93.             "#":  &null            # ignore
  94.             default: error()
  95.             }                # end case
  96.          }                # end scan
  97.       }                    # end while
  98.  
  99.    write("link ",args[1] | "recog")    # link main procedure
  100.    write("link matchlib")        # link built-in symbols
  101.    write("global goal\n")        # write out global declaration
  102.    write("procedure init()")        # write out initialization procedure
  103.    write("   goal := ",goal,"_")
  104.    write("   return")
  105.    write("end")
  106.  
  107. end
  108.  
  109. #
  110. #  Transform a production.
  111. #
  112.  
  113. procedure transprod()
  114.  
  115.    {
  116.       sym := tab(many(nchars)) &    # get the nonterminal name
  117.       =">::=" 
  118.       } | error()            # catch syntactic error
  119.    write("record ",sym,declend,"(alts)")# record declaration
  120.    write("procedure ",sym,procend)    # procedure header
  121.    write("   suspend {")        # begin the suspend expression
  122.    writes("      ",sym,declend,"(")    # write indentation
  123.    transalts()                # transform the alternatives
  124.    write(")")
  125.    write("      }")            # end the suspend expression
  126.    write("end")                # end the procedure declaration
  127.    write()                # space between declarations
  128.    /goal := sym                # first symbol is goal
  129.  
  130. end
  131.  
  132. #
  133. #  Transform a sequence of alternatives.
  134. #
  135. procedure transalts()
  136.    local alt                # an alternative
  137.  
  138.    while alt := tab(bal('|') | 0) do {    # process alternatives
  139.       writes("[")        # record for alternative
  140.       alt ? transseq()            # transform the symbols
  141.       if move(1) then writes("] | ")    # if more, close the parentheses
  142.                     # and add the alternation.
  143.       else {
  144.          writes("]")            # no more, so just close the parentheses
  145.          break
  146.          }                # end else
  147.       }                    # end while
  148.  
  149. end
  150.  
  151. #
  152. #  Transform a sequence of symbols.
  153. #
  154. procedure transseq()
  155.  
  156.    repeat {
  157.       transsym()            # process a symbols
  158.       if not pos(0) then writes(" , ")    # if there's more, provide concatenation
  159.       else break            # else get out and return
  160.       }                    # end while
  161.  
  162.    return
  163.  
  164. end
  165.  
  166. #
  167. #  Transform a symbol.
  168. #
  169. procedure transsym()
  170.    local group
  171.  
  172.    if ="<" then {            # if it's a nonterminal
  173.       {                    # write it with suffix.
  174.          writes(tab(many(nchars)),procend) &
  175.          =">"                # get rid of closing bracket
  176.          } | error()            # or catch the error
  177.       }                    # end then
  178.  
  179.    else if ="(" then {            # if it's a parenthesis, pass it
  180.       writes("(")            # along and call transseq()
  181.       group := tab(bal(')')) | error()
  182.       group ? transalts()
  183.       writes(")")
  184.       move(1)
  185.       }
  186.                     # else transform nonterminal string
  187.    else writes("=",image(tab(upto('<') | 0)))
  188.  
  189.    return
  190.  
  191. end
  192.  
  193. #
  194. #  Issue error message and terminate execution.
  195. #
  196. procedure error()
  197.  
  198.    stop("*** malformed definition: ",tab(0))
  199.  
  200. end
  201.